class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        # 获取两个字符串的长度
        m, n = len(word1), len(word2)

        # 创建动态规划表格，dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 初始化边界情况
        # 如果 word2 为空，则需要删除 word1 的所有字符
        for i in range(m + 1):
            dp[i][0] = i

        # 如果 word1 为空，则需要插入 word2 的所有字符
        for j in range(n + 1):
            dp[0][j] = j

        # 填充dp表格
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 如果当前字符相同，不需要操作
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    # 取三种操作中的最小值：
                    # 1. 替换操作：dp[i-1][j-1] + 1
                    # 2. 删除操作：dp[i-1][j] + 1
                    # 3. 插入操作：dp[i][j-1] + 1
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1]
                                   [j], dp[i][j - 1]) + 1

        # 返回将word1转换为word2所需的最少操作数
        return dp[m][n]
